'''
https://leetcode.cn/problems/find-minimum-in-rotated-sorted-array
'''
from typing import List


class Solution:
    def findMin(self, nums: List[int]) -> int:
        if len(nums) == 1 or nums[0] < nums[-1]:
            return nums[0]
        k = 0
        if nums[0] > nums[-1]:
            # 二分找到峰值点,
            #   1)v[m] < v[-1]: k在左侧
            #       else: k可能在正确的区间,可以动 l
            #   2)  在1)的条件下 v[l]一定 < v[m], 动l
            l, r = 0, len(nums) - 1
            while l <= r:
                mid = l + r >> 1
                if nums[mid] > nums[mid+1]:
                    k = mid
                    break
                elif nums[mid] < nums[-1]:
                    r = mid - 1
                else:
                    l = mid + 1
        return nums[k] + 1